package com.cat.math;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/prime-pairs-with-target-sum/
 * @create 2025/10/15 21:05
 * @since JDK17
 */

public class Solution08 {
    static int N = ((int) (1e6 + 10));
    static boolean[] isPrime = new boolean[N];
    static {
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i < N; i++) {
            if (!isPrime[i]) {
                for (long j = (long) i * i; j < N; j += i) {
                    isPrime[(int) j] = true;
                }
            }
        }
    }

    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 2; i <= n / 2; i++) {
            if (!isPrime[i] && !isPrime[n - i]) {
                ans.add(List.of(i, n - i));
            }
        }
        return ans;
    }
}
